<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Title</title>
</head>
<body>
<p>
  计数排序使用一个用来存储每个元素在原始数组中出现次数的临时数组。在所有元素都计数完成后，临时数组已排好序并可迭代以构建排序后的结果数组。<br>
  计数排序就是一种时间复杂度为 O(n) 的排序算法，该算法于 1954 年由 Harold H. Seward 提出。在对一定范围内的整数排序时，它的复杂度为 O(n+k)（其中 k 是整数的范围大小）。
  缺点：<br>
    浪费空间 <br>
    不能有负数
</p>

<script>
	{
		function countSort (arr) {
			const len = arr.length
			if (len <= 1) return arr

			const max = Math.max(...arr)
			const newArr = new Array(max + 1)

			for (let i = 0; i < len; i ++) {
				if (newArr[arr[i]]) {
					newArr[arr[i]] ++
				} else {
					newArr[arr[i]] = 1
				}
			}

			const rst = []

			// 最好用forEach 因为它不会把数组中的empty遍历出来 只会遍历出来有值的 即使你是undefined也能遍历出来
			// newArr.forEach((count, item) => {
			// 	while (count) {
			// 		rst.push(item)
			//     count--
			//   }
			// })

			// for循环可以把数组中的empty项遍历出来 值是undefined
			for (let i = 0; i < newArr.length; i ++) {
				let count = newArr[i]
				while (count) {
					rst.push(i)
					count --
				}
			}

			return rst
		}

		console.log(countSort([9, 5, 3, 4, 5, 100, 2, 1, 0]))
  }
</script>

<script>
	{
		function countSort (arr) {
			if (arr.length <= 1) return arr

      const max = Math.max(...arr)
      const newArr = new Array(max + 1)

      for (let i = 0; i < arr.length; i ++) {
				if (newArr[arr[i]] == null) {
					newArr[arr[i]] = 0
        }
	      newArr[arr[i]]++
      }

			const rst = []
      let i = 0
      newArr.forEach((count, item) => {
        while (count > 0) {
					rst[i++] = item
					count --
        }
      })

      return rst
    }
		console.log(countSort([9, 5, 3, 4, 5, 100, 2, 1, 0]))

  }
</script>

<script>
  function countSort (arr) {
    if (arr.length <= 1) return arr

    // 找到arr中最大值
    // const max = getMax(arr)
    const max = Math.max(...arr)
    const newArr = new Array(max + 1)

    for (let i = 0; i < arr.length; i ++) {
      if (!newArr[arr[i]]) {
        newArr[arr[i]] = 0
      }
      newArr[arr[i]] ++
    }

    const result = []
    let index = 0
    newArr.forEach((count, item) => {
      while (count > 0) {
        result[index++] = item
        count --
      }
    })
    return result
  }

  function getMax (arr) {
    let max = arr[0]
    for (let i = 1; i < arr.length; i ++) {
      if (arr[i] > max) {
        max = arr[i]
      }
    }
    return max
  }

  const arr = [9, 5, 3, 4, 5, 100, 2, 1, 0]
  // 返回新数组，不改变原数组，不能有负数
  const newArr = countSort(arr)
  console.log(newArr)
</script>
</body>
</html>
